package Other;

import java.util.Arrays;

public class leet_53 {
    public static void main(String[] args) {
        int[] nums = new int[]{-2,1,-3,4,-1,2,1,-5,4};
        Solution_53 p = new Solution_53();
        int[] result = p.maxSubArray(nums);
        System.out.println(Arrays.toString(result));
    }
}

class Solution_53 {
    public int[] maxSubArray(int[] nums) {
        int[] maxValue = moveWindowDiff(nums);
        return maxValue;
    }

    /**
     * 贪心算法
     * 定一个数组int[] result 存储每个位置的值，
     * 进行比较 nums[n~i]与nums[i]进行比较如果此时 nums[i] 比之前累和要大，
     * 说明再往后走也不可能比当前值大。丢弃原来的数组
     * 进行上面操作的同时需要自己维护 maxNums 来记录最大值与上面得到数组值进行比较
     * @param nums 传入的数组
     * @return 最大值
     */
    public int moveWindow(int[] nums){
        if (nums.length==0){
            return 0;
        }

        int maxNums = nums[0];
        int prev = nums[0];
        for(int i=1; i<nums.length; i++){
            // nums[n~i] 与 nums[i] 进行比较
            prev = Math.max(nums[i], prev+nums[i]);
            // maxNums 与 目前维护的子序列进行比较
            maxNums = Math.max(prev, maxNums);
        }
        return maxNums;
    }

    /**
     * 增加点难度 返回数组
     *
     * @param nums 传入数组
     * @return 返回一个数组
     */
    public int[] moveWindowDiff(int[] nums){
        if (nums.length==0){
            return null;
        }

        int maxNums = nums[0];
        int prev = nums[0];
        // 定义左右2个指针的位置，这个2个是当前维护数组的指针
        int left = 0;
        int right = 0;
        // 定义2个指针 最大子序列的指针
        int maxLeft = 0;
        int maxRight = 0;
        for(int i=1; i<nums.length; i++){
            // nums[n~i] 与 nums[i] 进行比较
            if(prev+nums[i] < nums[i]){
                prev = nums[i];
                // 移动左右指针
                left = i;
            }else{
                prev = prev+nums[i];
            }
            right = i;

            // maxNums 与 目前维护的子序列进行比较
            if(maxNums <= prev){
                maxLeft = left;
                maxRight = right;
                maxNums = prev;
            }
        }

        // 拿到对应数组
        int[] result=new int[maxRight-maxLeft+1];
        for(int i=maxLeft,tmpNum = 0; i<=maxRight; i++, tmpNum++){
            result[tmpNum]=nums[i];
        }
        return result;
    }

}

